package Algorithm.dynamicProgramming.knapsackDp;

/**
 * 494. 目标和 https://leetcode.cn/problems/target-sum/
 * 题目简述：给定一个自然数数组，从中选择子集求和，减去剩下的子集和，使运算结果为target，有多少种选择方法
 */
public class FindTargetSumWays {

    public static void main(String[] args) {
        new FindTargetSumWays().findTargetSumWays(new int[]{0,0,1}, 1);
    }

    /**
     * 思路：01背包-组合问题。left-right=target, left+right=sum。left=(target+sum)/2，设为w。
     *      即求从背包中取物品，使价值总和为w有多少种组合方法。
     * 1. 定义dp：dp[i][j]为从前i个物品中选，装满j有多少种方法
     * 2. 状态转移公式：若不能选第i件物品，即其重量直接超过了j或者选了就无法装满剩余容量，则dp[i][j] = dp[i-1][j];
     *            否则分为以下两种情况，dp[i][j] = 情况1 + 情况2
     *            （1）不选第i件物品，dp[i][j] = dp[i-1][j]
     *            （2）选第i件物品，若容量够且dp[i-1][j-nums[i-1]]不为0，则dp[i][j]=dp[i-1][j-nums[i-1]]，否则也为0
     * 3. 初始化：dp[0][0] = 1，dp[0][j] = 0。注意这里只能将dp[0][0]初始化为1，下层的dp[i][0]可能存在多种情况使组合和为0
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums)
            sum += num;
        if ((target+sum) % 2 != 0) return 0;
        int w = (target+sum) / 2;
        //由于价值都>=0，若背包重量为负，则不存在方法
        if (w < 0) return 0;
        int[][] dp = new int[nums.length+1][w+1];
        dp[0][0] = 1;//初始化
        for (int i = 1;i <= nums.length;i++) {
            for (int j = 0;j <= w;j++) {
                if (j < nums[i-1] || dp[i-1][j-nums[i-1]] == 0)
                    dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            }
        }
        return dp[nums.length][w];
    }
}
